package com.justnow.offer;

import java.util.ArrayList;
import java.util.List;

/**
 * @author justnow
 * Created on 2020-09-16
 * Description
 *
 * 全排列的交换方法
 */
public class Solution19_1 {

    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        dfs(0, nums);
        return res;
    }

    public void dfs(int x, int[] nums) {
        //x表示交换的位置，当交换的位置为length-1时，表明到最后一个元素了
        //因为最后一个元素，不需要进行交换，所以直接将这次交换的结果返回到结果集合中
        if (x == nums.length - 1) {
            List<Integer> temp = new ArrayList<>();
            for (int num : nums) {
                temp.add(num);
            }
            res.add(temp);
        }


        /**nums = {1, 2, 3}
         * x = 0
         * for {
         *     i = 0;
         *     swap(0, 0); {1, 2, 3}
         *     dfs(x = 1) {
         *          for {
         *              i = 1;
         *              swap(1, 1) {1, 2, 3};
         *              dfs(x = 2) {
         *                  temp.add
         *              }
         *              swap(1, 1);
         *              ----
         *              i = 2;
         *              sawp(2, 1) {1, 3, 2}
         *              dfs(x = 3) {
         *                  temp.add
         *              }
         *              swap(2, 1) {1, 2, 3}
         *          }
         *     }
         *     swap(0, 0):{1, 2, 3};
         *     ----
         *     i = 1;
         *     swap(1, 0) {2, 1, 3};
         *     dfs(x = 1) {
         *          swap(1, 1)
         *     }
         * }
         */
        for (int i = x; i < nums.length; i++) {
            swap(i, x, nums);
            dfs(x + 1, nums);
            swap(i, x, nums);
        }
    }

    public void swap(int i, int x, int[] nums) {
        int temp = nums[i];
        nums[i] = nums[x];
        nums[x] = temp;
    }

}
